package com.ly.algorithm.leetcode.tree;

import java.util.*;

/**
 * @Classname Problem113
 * @Description
 * 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 示例:
 * 给定如下二叉树，以及目标和 sum = 22，
 *
 *               5
 *              / \
 *             4   8
 *            /   / \
 *           11  13  4
 *          /  \    / \
 *         7    2  5   1.txt
 * 返回:
 *
 * [
 *    [5,4,11,2],
 *    [5,8,4,5]
 * ]
 *
 * @Date 2020/9/26 11:18
 * @Author 冷心影翼
 */
public class Problem113 {
    public static void main(String[] args) {
        Solution113 solution113 = new Solution113();
        TreeNode treeNode = new TreeNode(5);
        treeNode.left = new TreeNode(4);
        treeNode.right = new TreeNode(8);
        treeNode.right.left = new TreeNode(13);
        treeNode.right.right = new TreeNode(4);
        treeNode.right.right.right = new TreeNode(1);
        treeNode.right.right.left = new TreeNode(5);
        treeNode.left.left= new TreeNode(11);
        treeNode.left.left.left = new TreeNode(7);
        treeNode.left.left.right = new TreeNode(2);
        TreeNode t2 = new TreeNode(-2);
        t2.left= new TreeNode(-3);

        List<List<Integer>> lists = solution113.pathSum(treeNode, 22);
//        List<List<Integer>> lists2 = solution113.pathSum(t2, -5);
        lists.forEach(System.out::print);
    }
}

class Solution113 {
    public List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root == null) {
            return res;
        }
        preOrder(new ArrayList<>(),root,sum);
        return res;
    }

    public void preOrder(List<Integer> r,TreeNode root,int n) {
        n = n-root.val;

//        if(n<0) {
//            return;
//        }

        if(n == 0  && root.right == null && root.left == null) {
            List<Integer> copy = new ArrayList<>();
            copy.addAll(r);
            copy.add(root.val);
            res.add(copy);
            return;
        }
        r.add(root.val);
        if(root.left!=null)
            preOrder(r,root.left,n);
        if(root.right!=null)
            preOrder(r,root.right,n);
        r.remove(r.get(r.size()-1));
    }
}

class BestSolutuon113{
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        dfs(root, sum);
        return ret;
    }

    public void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0) {
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
        path.pollLast();
    }

}